#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int HASH=10007;
const int N=2050;
//自定义一个哈希表来去重
struct HashMap{
    int head[HASH];
    int Next[HASH];
    //表的大小
    int size;
    unsigned long long state[N];
    int f[N];
    void init(){
        size=0;
        memset(head,-1,sizeof(head));
    }
    int insert(unsigned long long val,int _id){
        //压缩下标
        int h=val%HASH;
        for(int i=head[h];i!=-1;i=Next[i]){
            if(val==state[i]){
                int tmp=f[i];
                f[i]=_id;
                return tmp;
            }
        }
        f[size]=_id;
        state[size]=val;
        Next[size]=head[h];
        head[h]=size++;
        return 0;
    }
}H;
const int Seed=13331;
unsigned long long p[N];
unsigned long long s[N];
char str[N];
//ans[l][r]表示区间[l,r]不同子串个数
int ans[N][N];
int main(void){
    //初始化p数组表示seed的n次幂
    p[0]=1;
    for(int i=1;i<N;i++){
        p[i]=p[i-1]*Seed;
    }
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",str);
        int n=strlen(str);
        s[0]=0;
        //预处理哈希值前缀和
        //hash[l,r]=hash[r]-seed^(r-l+1)*hash[l-1]
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]*Seed+str[i-1];
        }
        memset(ans,0,sizeof(ans));
        //枚举子串长度
        for(int L=1;L<=n;L++){
            //初始化哈希表
            H.init();
            //枚举起点
            for(int i=1;i+L-1<=n;i++){
                //枚举区间加入哈希表
                int l=H.insert(s[i+L-1]-s[i-1]*p[L],i);
                ans[i][i+L-1]++;
                ans[l][i+L-1]--;
            }
        }
        for(int i=n;i>=0;i--){
            for(int j=i;j<=n;j++){
                ans[i][j]+=ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
            }
        }
        int m,u,v;
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&u,&v);
            printf("%d\n",ans[u][v]);
        }
    }
    return 0;
}